//
// Created by Administrator on 2023-7-12
// 希尔排序
//

#include <iostream>
#include "arrUtil.h"
using namespace std;


int main()
{
//    int a[] = {9, 7, 5, 0, 3, 1};
//    shell(a, 6);
    vector<int> a;
    randVector(a,600);
    int len = a.size();
    int step = len / 2;
    while (step)
    {
        for (int i = 0; i < len - step; i += step)
        {
            int j = i;
            int cur = a[j + step];
//            cout<<cur<<' ';
            while (j >= 0 && cur < a[j])
            {
                a[j + step] = a[j];
                j -= step;
            }
            a[j+step] = cur;
        }
        step /= 2;
//        cout << endl;
    }
//    for (int i:a)
//        cout << i << ' ';
    cout<<endl<<checkSortVector(a);
    return 0;
}